/**
 * 714. 买卖股票的最佳时机含手续费
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/
 */
public class Solutions_714 {
    public static void main(String[] args) {
        int[] prices = {1, 3, 2, 8, 4, 9};
        int fee = 2;  // output: 8  ((8 - 1) - 2) + ((9 - 4) - 2) = 8

//        int[] prices = {1, 3, 2, 8, 9};
//        int fee = 2;  // output: 6  (9 - 1) - 2 = 6

        int result = maxProfit(prices, fee);
        System.out.println(result);
    }

    public static int maxProfit(int[] prices, int fee) {
        if (prices == null || prices.length < 2) {
            // 小于 2 时，无法完成购买并卖出
            return 0;
        }
        // 成本（在没有利润的情况下，买入后，成本就是负数）
        int have = prices[0] * -1;
        // 利润（未卖出时，利润为 0）
        int profit = 0;

        for (int i = 1; i < prices.length; i++) {
            // 在持有成本 have 的情况下，若在 prices[i] 时卖出，那么可以获得 curProfit 的利润
            int curProfit = have + prices[i] - fee;

            if (curProfit > profit) {
                // 此次卖出，可以盈利，但是不一定可以达到最大利润
                // 所以并不是真正地卖出，但是所得利润需要记录下来
                profit = curProfit;
                continue;
            }
            // 在已有收益 profit 的情况下，如果买入 prices[i] 后，成本就变成了 profit - prices[i]（原本成本为负数）
            if (profit - prices[i] > have) {
                // 可以真正地卖出原有的股票，更新持有成本为 profit - prices[i]
                have = profit - prices[i];
            }
            // 否则继续持有原股票，等待更大的卖出点
        }
        return profit;
    }
}
